//----------------------------------------------------------------------SPFA
#define EMPTY (qh==qr)
#define PUSHBK(x) do{Q[qr]=x;vis[x]=1;qr++;qn++;tot+=f[x];}while(0)
#define PUSHFT(x) do{qh--;Q[qh]=x;vis[x]=1;qn++;tot+=f[x];}while(0)
#define POP(x) do{while(f[Q[qh]]*qn>tot){Q[qr]=Q[qh];qr++;qh++;}x=Q[qh];vis[x]=0;qh++;qn--;tot-=f[x];}while(0)
typedef long long  LL;
unsigned n,//点数
	 to[150000],//边指向的节点
	 p[150000],//下一条边
	 v[150000],//边权
	 e,//边数
	 h[40001],//头节点
	 vis[40001];
unsigned f[40001],//存放最优值
	 Q[65536];//循环队列
unsigned short qh,qr;//队首队尾,自然溢出代替取模
LL tot,qn;//用于Large Label Last
void spfa(int s)
{
	int tmp;
	f[s]=0;qh=0;qr=0;tot=0;qn=0;
	PUSHBK(s);
	while(!EMPTY){
		POP(tmp);
		for(unsigned i=h[tmp];i;i=p[i]){
			if(f[to[i]]>f[tmp]+v[i]){
				f[to[i]]=f[tmp]+v[i];
				if(!vis[to[i]]){	//Small Label First
					if(f[Q[qh]]>f[to[i]])PUSHFT(to[i]);
					else PUSHBK(to[i]);
				}
			}
		}
	}

}
